Two recurring central topics in information theory are efficient compression and reliable transmission of data. In the fast 20 years or so communications and information technologies have fundamentally changed how we access information, interact as a society, and communicate. Today, these central topics are everywhere in our daily lives whether they arise in our use of portable electronic devices for mobile communications, multimedia streaming/downloading, Internet access, etc or fixed electronic devices for content acquisition, watching our favorite television show, storing family photos, etc. Further, the ubiquitous nature of computing devices, cloud based storage, and the enhanced speed performance of the Internet mean that increasing our lives exploits remote stores of data.
With respect to data compression this can be either lossless or lossy. If the data consists of bank records, medical records, or personal details we cannot afford to lose any information. In such cases, the compression is achieved by exploiting patterns and redundancies in the data to reduce the volume of data that must be transferred. For example, the commonly used “zip” format for storing electronic data is a good example of a lossless compression scheme. In contrast, lossy compression involves loss of information and is commonly used for multimedia data like images, music or video. Common examples include the JPEG image format and the MP3 music format. So if we lose data why use lossy compression at all? On the one hand this is due to necessity as most physical phenomena are real valued and storing them in digital form must involve some form of quantization, and hence, some loss of information. On the other hand, a video captured in high-quality digital form can typically be compressed substantially with very little loss in perceptual quality to the viewer but significant reduction in memory storage requirements or transfer time from a remote source. Accordingly, between a given source and a measure of quality, there is a trade-off between storage requirement and quality. In many instances this trade-off can be exploited to adapt a source coding scheme to a given situation such that for example, a user with small bandwidth may be happy to get a low quality video if the alternative is not to be able to watch the video at all.
The second central topic of information theory is the transmission of data through a noisy medium. Typically, to make communication reliable in the presence of noise, redundancy in the data is added before transmission as the intended receiver only has access to a noisy version of the data. However, if the redundancy is added through coding then it is possible to reconstruct the original data at the receiver in the presence of noise, which results in incorrect data being received through decision making processes at the receiver. Coding is therefore a central and essential element in any communication systems we access ourselves or accessed in delivering the electronic content we seek to transmit and/or retrieve. However, adding this redundancy comes at the cost of reducing the effective rate of data transmission for a given data transmission rate as in addition to the data we must also transmit the redundant data.
In 1948, Shannon, “A Mathematical Theory of Communication” (Bell Sys. Tech. J., Vol. 27, pp 379-423), established the existence of a maximum rate, called the channel capacity, at which information can be reliably transmitted over a channel with noise, and the existence of codes which enable data transmission at that rate. Since then, different capacity-approaching codes have been created, see for example C. Berrou et al in “Near Shannon Limit Error-Correcting Coding and Decoding: Turbo-Codes” (Proc. ICC 93, Vol. 2, pp 1064-1070) and R. Gallager in “Low-Density Parity-Check Codes” (IRE Trans. Inf. Theory, Vol. 8, pp. 21-28). However, designing capacity-achieving codes with an explicit construction eluded researchers until Ankan proposed polar codes, see E. Ankan, “Channel Polarization: A Method for Constructing Capacity-Achieving Codes for Symmetric Binary-Input Memoryless Channels” (IEEE Trans. on Inf. Theory, Vol. 55, pp. 3051-3073), and proved that these polar codes asymptotically achieve the capacity of binary-input symmetric memoryless channels with increasing code length. Later works proved that polar codes achieve the channel capacity for any discrete memoryless channel and, by extension, for any continuous memoryless channel, see E. Sasoglu et al in “Polarization for Arbitrary Discrete Memoryless Channels” (Proc. IEEE Inf. Theory Workshop, 2009, pp. 144-148). Moreover, Arikan provided an explicit construction method for polar codes and showed that they can be efficiently encoded and decoded with complexity O(N*log N), where N is the code length. Additionally, polar codes have also been shown to be beneficial in solving other information theoretic problems in an efficient manner, see for example H. Mandavifar et al in “Achieving the Secrecy Capacity of Wiretap Channels Using Polar Codes” (IEEE Trans. on Inf. Theory, Vol. 57, pp. 6428-6443), N. Hussami et al in “Performance of Polar Codes for Channel and Source Coding” (IEEE ISIT 2009), and S. B. Korada et al in “Polar Codes are Optimal for Lossy Source Coding” (IEEE Trans. on Inf. Theory, Vol. 56, pp. 1751-1768).
However, whilst demonstrating these benefits, polar codes also require large code lengths to approach the capacity of the underlying channel, for example, N>220, in which case, over 20 million computational nodes are required to decode one codeword. This presents a real challenge when it comes to implementing the decoders, for example successive cancellation (SC) decoders, in hardware. However, despite these large code lengths, polar codes beneficially have two desirable properties for hardware implementation. First, they are explicitly described in a recursive framework such that this regular structure enables resource sharing and simplification of the scheduling and the architecture. Second, unlike many common capacity-approaching codes, polar codes do not require any kind of randomness to achieve good error correcting performance which helps avoid memory conflicts and graph-routing problems during the implementation.
However, to date within the prior art research has been heavily focused to improving the error-correction performance of polar codes at moderate lengths and implementations such as Belief Propagation, see for example Hussami; Simplified Successive Cancellation, see for example A. Alamdar-Yazdi et al in “A simplified Successive Cancellation Decoder for Polar Codes” (IEEE Comm. Lett., Vol. 15, pp. 1378-1380); and Look-Ahead Technique, see for example C. Zhang et al in “Reduced-Latency SC Polar Decoder Architectures” (Proc. of IEEE Int. Conf. Comms., pp. 3520-3524, June 2012). These prior art approaches include list decoding, see for example I. Tal et al in “List Decoding of Polar Codes” (Proc. ISIT, 2011); non-binary polar codes, see for example R. Mori et al in “Non-Binary Polar Codes using Reed-Solomon Codes and Algebraic Geometry Codes” (Proc. IEEE Inf. Theory Workshop, 2010, pp 1-5); and complex construction methods, see for example S. B. Korada et al in “Polar Codes: Characterization of Exponent, Bounds, and Constructions” (IEEE Trans. Inf. Theory, Vol. 56, pp. 6253-6264). However, in contrast, the inventors have addressed implementing the standard SC decoding algorithm, as any improvements to such an SC decoding implementation can benefit more complex decoding algorithms since all polar codes are based on the same recursive construction. Beneficially, such low-complexity SC decoders implemented according to embodiments of the invention enable the use of longer polar codes and hence allow data to be transmitted over channels close to the channel capacity limit.
The original description of the SC decoding algorithm by Ankan mapped the decoder to a factor graph of the polar code, without going into any details of a specific architecture. Accordingly, the resulting SC decoder for the factor graph of Ankan includes N*log2 N node processing elements (PEs), requires N*log2 N memory elements (MEs), and takes (2N−2) steps to decode one codeword. Accordingly it would be beneficial to address architectures and decoding processes that reduce the complexity of the SC decoder both in terms of the number of processing elements required, but also the number of memory elements and the number of steps required to decode a codeword.
It would be further beneficial if the complexity of the processing elements was reduced thereby allowing the die footprint of any implemented hardware circuit to be reduced thereby lowering cost. Similarly where large code lengths are employed a large number of memory elements are required with multiple read/write processes such that it would be beneficial for the structure and configuration of the memory to be improved to the decoder architecture. It would also be evident to one skilled in the art that in addition to reducing the number of elements that other factors impacting the overall performance of the decoder should also be addressed including, for example, latency. Beneficially, architectures and design methodologies established by the inventors address such issues whilst reducing overall complexity, as well as providing methodologies for adjusting decoder design based upon requirements including, but not limited to, cost (e.g. through die area) and speed (e.g. through latency, number of cycles, number of elements etc).
Other aspects and features of the present invention will become apparent to those ordinarily skilled in the art upon review of the following description of specific embodiments of the invention in conjunction with the accompanying figures.